#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define pii pair<int,int>
#define int long long

const int N = 100005, M = 2000010;
int p[N], cnt, head[N], nxt[M], to[M], rhead[N];
int n, m;
int mi[N], mx[N];
bool vis[N];


void spfa1(int s) {
	memset(mi, 0x3f, sizeof mi);
	memset(vis, 0, sizeof vis);
	queue<int> q;
	mi[s] = p[s];
	vis[s] = 1;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = head[u]; i; i = nxt[i]) {
			int v = to[i], z = min(p[v], mi[u]);
			if (mi[v] > z) {
				mi[v] = z;
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

void spfa2(int s) {
	memset(mx, 0, sizeof mi);
	memset(vis, 0, sizeof vis);
	queue<int> q;
	mx[s] = p[s];
	vis[s] = 1;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = rhead[u]; i; i = nxt[i]) {
			int v = to[i], z = max(p[v], mx[u]);
			if (mx[v] < z) {
				mx[v] = z;
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

void add(int x, int y, int* head) {
	nxt[++cnt] = head[x];
	head[x] = cnt;
	to[cnt] = y;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> p[i];
	for (int i = 1, u, v, z; i <= m; i++) {
		cin >> u >> v >> z;
		add(u, v, head); add(v, u, rhead);
		if (z == 2) {
			add(v, u, head); add(u, v, rhead);
		}
	}
	spfa1(1);
	spfa2(n);

	int res = 0;
	for (int i = 1; i <= n; i++) res = max(res, mx[i] - mi[i]);
	cout << res << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
//int n, p, k;
//int dis[1000006], head[100006], to[1000007], nxt[1000007], cnt, w[1000007];
//bool vis[1000006];
//
//
//void add(int x, int y, int z) {
//	nxt[++cnt] = head[x];
//	head[x] = cnt;
//	w[cnt] = z;
//	to[cnt] = y;
//}
//
//bool check(int x) {
//	memset(dis, 0x3f, sizeof(dis));
//	memset(vis, 0, sizeof(vis));
//	dis[1] = 0;
//	deque<int> q;
//	q.push_back(1);
//	while (!q.empty()) {
//		int u = q.front(); q.pop_front();
//		if (vis[u])continue;
//		vis[u] = 1;
//		for (int i = head[u]; i; i = nxt[i]) {
//			int v = to[i], wei = w[i];
//			if (w[i] > x) {
//				if (!vis[v] && dis[v] > dis[u] + 1) {
//					dis[v] = dis[u] + 1;
//					q.push_back(v);
//				}
//			}
//			else {
//				if (!vis[v] && dis[v] > dis[u]) {
//					dis[v] = dis[u];
//					q.push_front(v);
//				}
//			}
//		}
//	}
//	return dis[n] <= k;
//}
//
//
//void solve() {
//	cin >> n >> p >> k;
//	for (int i = 1, x, y, z; i <= p; i++) {
//		cin >> x >> y >> z;
//		add(x, y, z); add(y, x, z);
//	}
//	int l = 0, r = 1e9, mid;
//	while (l < r) {
//		mid = (l + r) >> 1;
//		if (check(mid)) {
//			r = mid;
//		}
//		else
//			l = mid + 1;
//	}
//	if (l == 1e9)cout << -1;
//	else cout << l;
//}

//int n, p, k;
//int dis[1000006], head[1000006], to[10000007], nxt[10000007], cnt, w[10000007];
//bool vis[1000006];
//priority_queue<pii, vector<pii>, greater<pii> >q;
//
//void add(int x, int y, int z) {
//	nxt[++cnt] = head[x];
//	head[x] = cnt;
//	w[cnt] = z;
//	to[cnt] = y;
//}
//
//void dj() {
//	memset(dis, 0x3f, sizeof(dis));
//	dis[1] = 0;
//	q.push({ 0,1 });
//	while (!q.empty()) {
//		auto cur = q.top(); q.pop();
//		int u = cur.second, d = cur.first;
//		if (vis[u])continue;
//		vis[u] = 1;
//		for (int i = head[u]; i; i = nxt[i]) {
//			int v = to[i];
//			int z = max(dis[u], w[i]);
//			if (!vis[v] && dis[v] > z) {
//				dis[v] = z;
//				q.push({ z,v });
//			}
//		}
//	}
//}
//
//
//cin >> n >> p >> k;
//for (int i = 1, x, y, z; i <= p; i++) {
//	cin >> x >> y >> z;
//	add(x, y, z); add(y, x, z);
//	for (int j = 1; j <= k; j++) {
//		add(x + (j - 1) * n, y + j * n, 0);
//		add(y + (j - 1) * n, x + j * n, 0);
//		add(x + j * n, y + j * n, z);
//		add(y + j * n, x + j * n, z);
//	}
//}
//
//for (int i = 1; i <= k; i++) {
//	add(n * i, n * (i + 1), 0);
//}
//
//dj();
//
//if (dis[(k + 1) * n] == 4557430888798830399)cout << -1;
//else cout << dis[(k + 1) * n];
